package seqlist;

import com.sun.deploy.security.BadCertificateDialog;
import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;
import sun.text.resources.CollationData;

//车厢类
class Node{
    //存储具体元素
    int data;
    //存储下一节节点的地址
    Node next;

    public Node(int data) {
        this.data = data;
    }

    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }

}


//火车
public class SingelLinkedList {
    //当前实际存储的元素个数
    private  int size;
    //当前链表中存储的第一个结点
    private Node head;
    private Node dummyHead=new Node(-1);



   //在火车头部添加元素
    public void addFirst(int data){
        //当前火车中还没有结点
        if(size==0){
            Node node=new Node(data);
            head=node;
            size++;
        }else {
            //当前火车中已经有结点了
            Node node=new Node(data);
            node.next=head;
            head=node;
            size++;

        }
    }

    //在任意位置插入元素
    public void addIndex(int index,int data){
        Node node=new Node(data);
        Node prev=head;
        //先判断下标是否合法
        if(index<0 || index>size) {
            System.err.println("add index illegal");
        }
        for (int i = 0; i <index-1 ; i++) {
            prev=prev.next;
        }
        //此时已经找到了待插入结点的前驱结点
        //进行连接和脱钩操作
        node.next=prev.next;
        prev.next=node;
        size++;
    }


    //在火车的尾部插入元素
    public void addLast(int data){
       addIndex(size,data);
    }

    //查找单链表下标所对应的元素
    public int  get(int index){
        if(rangeCheck(index)){
            Node node=head;
            for (int i = 0; i < index; i++) {
                node=node.next;
            }
            //此时node指向待查找的元素
            int data=node.data;
            return data;
        }else{
            System.err.println("get index illegal");
            return -1;
        }
    }

    //查找单链表中包含的元素
    public boolean contains(int data){
        Node node=head;
        while(node!=null){
            if(node.data==data){
                return true;
            }else{
                node=node.next;
            }
        }
        return false;
    }



    //修改单链表中元素的值,并返回修改前的值
    public int set(int index,int data){
        if(rangeCheck(index)){
            Node node=head;
            for (int i = 0; i < index; i++) {
                node=node.next;
            }
            int oldvalue=node.data;
            node.data=data;
            return oldvalue;
        }else{
            System.err.println("set index illegal");
            return -1;
        }

    }

    //删除头节点
    public void removeFirst(){
        Node node=head;
        head=head.next;
        node.next=null;
        size--;
    }
//    删除下标为1的元素
    public void removeIndex(int index){
        if(rangeCheck(index)){
            if(index==0){
                removeFirst();
            }else {
                Node prev = head;
                for (int i = 0; i < index - 1; i++) {
                    prev = prev.next;
                }
                //此时prev就是待删除结点的前驱结点
                Node node=prev.next;
                //删除元素，并连接其余的元素
                prev.next = node.next;
                node.next = null;
                size--;
            }
        }else{
            System.err.println("remove index illegal");
        }
    }


    //删除单链表中第一个元素为二的结点
    public void removeVauleOnce(int data){
        if(head.data==data){
            removeFirst();
        }else{
            //此时第一个结点一定不是待删除的结点
            Node prev=head;
            while(prev.next!=null){
                if(prev.next.data==data){
                    //此时prev就是待删除结点的前驱结点
                    Node node=prev.next;
                    prev.next=node.next;
                    node.next=null;
                    size--;
                    break;
                }else{
                    prev=prev.next;
                }
            }
        }
    }

    //删除链表中所有元素为2的结点
    public void removeValueAll(int data){
        while (head!=null && head.data==data  ){
            Node node=head;
            head=head.next;
            node.next=null;
            size--;
        }
        if(head==null){
            //此时说明所有待删除的元素都已经删除完毕 链表为空了
            return;
        }else {
            //此时头节点已经处理完毕 且链表不为空
            Node prev = head;
            //此时头节点一定不是待删除的结点，所以要看prev.next是否为空
            while (prev.next != null) {
                if (prev.next.data == data) {
                    //此时Prev就是待删除元素的前驱结点
                    //node就是待删除的元素结点
                    Node node = prev.next;
                    prev.next = node.next;
                    node.next = null;
                    size--;
                } else {
                    prev = prev.next;
                }
            }
        }
    }





    //单链表下标的合法性检验
    private boolean rangeCheck(int index){
        if(index<0 || index>=size){
            return false;
        }
        return true;
    }
    //遍历链表
    public String toString(){
        String ret="";
        Node node=head;
        while(node!=null){
            ret+=node.data+"->";
            node=node.next;
        }
        ret+="NULL";
        return ret;
    }


    public static void main(String[] args) {

        SingelLinkedList singelLinkedList=new SingelLinkedList();
        singelLinkedList.addFirst(2);
        singelLinkedList.addFirst(2);
        singelLinkedList.addFirst(2);
        singelLinkedList.addLast(1);
        singelLinkedList.addIndex(2,4);
        //3->2->5->1->4
        System.out.println(singelLinkedList);
//        //5
//        System.out.println(singelLinkedList.get(2));
////        //true
//        System.out.println(singelLinkedList.contains(2));
//        //false
//        System.out.println(singelLinkedList.contains(20));
//        //4
//        System.out.println(singelLinkedList.set(4,7));
////        //3->2->5->1->7
//        System.out.println(singelLinkedList);
        singelLinkedList.removeIndex(2);
//        singelLinkedList.removeVauleOnce(3);
//        singelLinkedList.removeValueAll(2);
       System.out.println(singelLinkedList);
    }
}
